package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;

/**
  * 题目Id：498
  * 题目：对角线遍历
  * 日期：2023-08-20 19:49:34
*/
//给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。 
//
// 
//
// 示例 1： 
// 
// 
//输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
//输出：[1,2,4,7,5,3,6,8,9]
// 
//
// 示例 2： 
//
// 
//输入：mat = [[1,2],[3,4]]
//输出：[1,2,3,4]
// 
//
// 
//
// 提示： 
//
// 
// m == mat.length 
// n == mat[i].length 
// 1 <= m, n <= 10⁴ 
// 1 <= m * n <= 10⁴ 
// -10⁵ <= mat[i][j] <= 10⁵ 
// 
//
// Related Topics 数组 矩阵 模拟 👍 462 👎 0


public class DiagonalTraverse {
    public static void main(String[] args) {
        Solution solution = new DiagonalTraverse().new Solution();
        int[] diagonalOrder = solution.findDiagonalOrder(new int[][]{{7, 8, 9}});
        System.out.println(Arrays.toString(diagonalOrder));
        System.out.println("Hello world");
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {

        /**
         * 对角线遍历
         * 思路 数组 m*n
         * 求出对角线的条数   m+n-1
         *第i条对角线   从0开始
         * i是偶数从下网上遍历    开始节点   i<=m-1   (i,0)   i>m-1    (m-1,i-(m-1))
         * 奇数 从上往下遍历               i<n-1    (0,i)            (i-(n-1),n-1)
         */

        int m=mat.length,n=mat[0].length;
        ArrayList<Integer> list = new ArrayList<Integer>();
        int x = 0,y=0;
        for (int i = 0; i <=m+n-1; i++) {
            if(i%2==0){
                if(i<m){
                    x=i;y=0;
                    while (x>=0&&y<n) {
                        list.add(mat[x][y]);
                        x--;y++;
                    }
                }else {
                    x=m-1;y=i-m+1;
                    while (x>=0&&y<n) {
                        list.add(mat[x][y]);
                        x--;y++;
                    }
                }
            }else {
                if(i<=n-1){
                    x=0;y=i;
                    while (x<m&&y>=0) {
                        list.add(mat[x][y]);
                        x++;
                        y--;
                    }
                }else {
                    x=i-(n-1);y=n-1;
                    while (x<m&&y>=0) {
                        list.add(mat[x][y]);
                        x++;y--;
                    }
                }
            }

        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}
//leetcode submit region end(Prohibit modification and deletion)

} 
